package com.wujunshen.algorithm.leetcode.basic;

/**
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/3 23:19<br>
 */
public class 添加与搜索单词 {
  private final TrieNode root;

  public 添加与搜索单词() {
    root = new TrieNode();
  }

  public void addWord(String word) {
    root.insert(word);
  }

  public boolean search(String word) {
    return dfs(word, 0, root);
  }

  private boolean dfs(String word, int index, TrieNode node) {
    if (index == word.length()) {
      return node.isEnd();
    }
    char ch = word.charAt(index);
    if (Character.isLetter(ch)) {
      int childIndex = ch - 'a';
      TrieNode child = node.getChildren()[childIndex];
      return child != null && dfs(word, index + 1, child);
    } else {
      for (int i = 0; i < 26; i++) {
        TrieNode child = node.getChildren()[i];
        if (child != null && dfs(word, index + 1, child)) {
          return true;
        }
      }
    }
    return false;
  }
}

class TrieNode {
  private final TrieNode[] children;
  private boolean isEnd;

  public TrieNode() {
    children = new TrieNode[26];
    isEnd = false;
  }

  public TrieNode[] getChildren() {
    return children;
  }

  public boolean isEnd() {
    return isEnd;
  }

  public void insert(String word) {
    TrieNode node = this;
    for (int i = 0; i < word.length(); i++) {
      char ch = word.charAt(i);
      int index = ch - 'a';
      if (node.children[index] == null) {
        node.children[index] = new TrieNode();
      }
      node = node.children[index];
    }
    node.isEnd = true;
  }
}
